﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Security.AccessControl;
using System.Text;
using System.Threading.Tasks;

namespace Tree
{
    internal class binTree
    {
        class FindException: Exception 
        {
            public FindException() { }
            public FindException(string message) : base(message) { }
            public FindException(string message, Exception innerException) : base(message, innerException) { }
        }

        binTree? leftChild;
        binTree? rightChild;
        binTree? parent;
        double? weight;
        public binTree() { }
        public binTree(binTree? parent, double? value)
        {
            weight = value;
            this.parent = parent;
        }

        public void add(double value)
        {
            if (weight != null)
            {
                if (value > weight) addIfMore(value);
                else if (value < weight) addIfLess(value);
            }
            else weight = value;
            checkAVLCondition();
        }

        void addIfMore(double value)
        {
            if (rightChild != null) rightChild.add(value);
            else rightChild = new binTree(this, value);
        }

        void addIfLess(double value)
        {
            if (leftChild != null) leftChild.add(value);
            else leftChild = new binTree(this, value);
        }

        void checkAVLCondition()
        {
            int rightHeight = 0, leftHeight = 0, rightrightHeight = 0,
                rightleftHeight = 0, leftleftHeight = 0, leftrightHeight = 0;

            if (leftChild != null)
            {
                leftHeight = this.leftChild.findMaxDepth();
                if (leftChild.leftChild != null) leftleftHeight = this.leftChild.leftChild.findMaxDepth();
                if (leftChild.rightChild != null) leftrightHeight = this.leftChild.rightChild.findMaxDepth();
            }
            if (rightChild != null)
            {
                rightHeight = this.rightChild.findMaxDepth();
                if (rightChild.leftChild != null) rightleftHeight = this.rightChild.leftChild.findMaxDepth();
                if (rightChild.rightChild != null) rightrightHeight = this.rightChild.rightChild.findMaxDepth();
            }

            if (leftrightHeight == rightHeight + 1)
            {
                leftChild.makeLeftRotation();
                makeRightRotation();
            }
            else if (leftHeight == rightHeight + 2) makeRightRotation();
            else if (rightleftHeight == leftHeight + 1)
            {
                rightChild.makeRightRotation();
                makeLeftRotation();
            }
            else if (rightHeight == leftHeight + 2) makeLeftRotation();
        }

        void makeRightRotation()
        {
            //X is the same as this tree
            binTree? A = this.leftChild, T2 = this.leftChild.rightChild;
            
            if (this.parent != null)
            {
                if (this == this.parent.rightChild) this.parent.rightChild = A;
                else this.parent.leftChild = A;
            }
            A.rightChild = this;
            A.parent = this.parent;
            this.parent = A;
            this.leftChild = T2;
        }

        void makeLeftRotation() {
            binTree? B = this.rightChild, T2 = this.rightChild.leftChild;
            if (this.parent != null)
            {
                if (this == this.parent.rightChild) this.parent.rightChild = B;
                else this.parent.leftChild = B;
            }
            B.leftChild = this;
            B.parent = this.parent;
            this.parent = B;
            this.rightChild = T2;
        }

        public void remove(double? value)
        {
            if (weight == null) throw new FindException("The Tree is empty!");
            else
            {
                if (value > weight && rightChild != null) rightChild.remove(value);
                else if (value < weight && leftChild != null) leftChild.remove(value);
                else if (value == weight) removeIfEquals();
                else throw new FindException("The value is not in Tree");
            }
        }

        void removeIfEquals()
        {
            if (leftChild == null && rightChild == null) removeIfNoChild();
            else if (leftChild != null && rightChild != null) removeIfTwoChild();
            else if (leftChild != null) removeIfOneChild(leftChild);
            else removeIfOneChild(rightChild);
        }


        void removeIfNoChild()
        {
            if (parent == null) weight = null;
            else parent.removeAloneChildFromParent(this);
        }
        void removeAloneChildFromParent(binTree child)
        {
            if (child.weight > this.weight) rightChild = null;
            else leftChild = null;
        }


        void removeIfOneChild(binTree child)
        {
            weight = child.weight;
            swapChildren(child);
        }
        void swapChildren(binTree child)
        {
            binTree copy = child;
            leftChild = copy.leftChild;
            rightChild = copy.rightChild;
            if (leftChild != null) leftChild.parent = this;
            if (rightChild != null) rightChild.parent = this;
        }


        void removeIfTwoChild()
        {
            binTree withoutRChild = leftChild.findWithoutRightChild();
            weight = withoutRChild.weight;
            withoutRChild.remove(withoutRChild.weight);
        }
        binTree findWithoutRightChild()
        {
            if (rightChild == null) return this;
            else return rightChild.findWithoutRightChild();
        }


        public void showLikeLine(string path = "")
        {
            if (leftChild != null) 
            { 
                leftChild.showLikeLine(path + "l"); 
            }
            Console.Write(" ({0}){1} ", path, weight);
            if (rightChild != null)
            {
                rightChild.showLikeLine(path + "r");
            }
        }


        int findMaxDepth()
        {
            int leftDepth = 0;
            int rightDepth = 0;
            if (leftChild == null && rightChild == null) return 1;
            if (leftChild != null) leftDepth = leftChild.findMaxDepth() + 1;
            if (rightChild != null) rightDepth = rightChild.findMaxDepth() + 1;
            
            return (leftDepth > rightDepth ? leftDepth : rightDepth);
        }

        public binTree getRoot()
        {
            if (this.parent == null) return this;
            else { return this.parent.getRoot(); }
        }
    }
}
